Many color image output devices are not capable of displaying all of the colors in an input digital image due to the fact that they must be stored in a memory buffer with a reduced bit-depth. Likewise, it may also be desirable to represent an image using a reduced bit-depth in order to reduce the amount of bandwidth needed for the transmission of an image, or the amount of memory needed to store an image. For example, many computers may use an 8-bit or a 16-bit color representation to store an image that is to be displayed on a soft-copy display such as a CRT or an LCD screen. Such representations allow only 256 and 65,536 unique color values, respectively. This is significantly less than the 16,777,216 possible color values associated with a typical 24-bit color image that is conventionally used in many digital imaging applications.
In applications where it is necessary to represent an input image using a reduced number of colors, it is necessary to determine the set of colors to be included in the reduced set of colors. In some cases, a reduced set of colors may be determined ahead of time independent of the particular image being encoded. For example, 3-bits of color information (8 different levels) may be used for the red and green channels of an image, and 2-bits of color information (4 different levels) may be used for the blue channel of an image. This produces a lattice of 8×8×4=256 different color values that can be used to represent the input image using an 8-bit representation. The input digital image can be converted to the 8-bit representation simply by taking the highest 2- or 3-bits of each of the corresponding RGB channels. The result is an image which has quantization errors that can produce visible contours in the image in many circumstances. One disadvantage of this method is that any particular image may not contain colors in all parts of color space. As a result, there may be some of the 256 color values that never get used. Consequently, the quantization errors are larger than they would need to be.
One method for minimizing the visibility of the quantization errors in the reduced bit-depth image is to use a multi-level halftoning algorithm to preserve the local mean of the color value. (For example see: R. S. Gentile, E. Walowit and J. P. Allebach, “Quantization and multilevel halftoning of color images for near original image quality,” J. Opt. Soc. Am. A 7, 1019–1026 (1990).)
Another method for minimizing the visibility of the quantization errors in the reduced bit-depth image is to select the palette of color values used to represent each image based on the distribution of color values in the actual image. This avoids the problem of wasting color values that will never be used to represent that particular image. Examples of such image dependent palette selection methods include vector quantization schemes, such as those described in R. S. Gentile, J. P. Allebach and E. Walowit, “Quantization of color images based on uniform color spaces,” J. Imaging Technol. 16, 11–21 (1990). These methods typically involve the selection of an initial color palette, followed by an iterative refinement scheme. Another approach, described in R. Balasubramanian and J. P. Allebach, “A new approach to palette selection for color images,” J. Imaging Technol. 17, 284–290 (1991), starts with all of the colors of an image and groups colors into clusters by merging one nearest neighbor pair of clusters at a time until the number of clusters equals the desired number of palette colors. A third class of vector quantization algorithms uses splitting techniques to divide the color space into smaller sub-regions and selects a representative palette color from each sub-region. In general, splitting techniques are computationally more efficient than either the iterative or merging techniques and can provide a structure to the color space that enables efficient pixel mapping at the output. (For a description of several such splitting techniques, see commonly assigned U.S. Pat. No. 5,544,284.)
While vector quantization mechanisms can yield high quality images, they are very computationally intensive. A sequential scalar quantization method is set forth by Allebach et al. in U.S. Pat. No. 5,544,284. This method sequentially partitions a histogram representing the distribution of the original digital color image values into a plurality of sub-regions or color space cells, such that each partitioned color cell is associated with a color in the output color palette. This method has the advantage that it is generally more computationally efficient than vector quantization schemes.
Image dependent palette selection methods have the significant advantage that they assign the palette colors based on the distribution of color values in a particular digital image. Therefore, they avoid the problem of having palette color values that never get used for a particular image. The various methods will generally tend to select palette colors that are representative of the most commonly occurring colors in the particular image. This has the result of reducing the average quantization errors throughout the image. However, in some cases, there may still be large quantization errors in important image regions. For example, consider the case where an image contains the face of a person that only occupies a small image region. The number of pixels in the image that represent skin-tone colors may be relatively small, and therefore the likelihood that palette colors get assigned to skin-tone colors will be low. As a result, when the image is represented by the set of chosen palette colors, there may be objectionable contours in the face. Since this image region may be very important to an observer, these artifacts may be much more objectionable than they would have been if they had occurred in other image regions. Other types of image content where quantization artifacts may be particularly objectionable would include neutral image regions, and blue sky image regions. Existing image dependent palette selection techniques do not provide any mechanism for minimizing the quantization artifacts in these important image regions unless they are large enough in size to comprise a significant portion of the distribution of image colors.